Gordov sinh ngày 30 tháng 12 năm 1896 tại làng Matveyevka thuộc Tỉnh bang Ufa, trong một gia đình nông dân. Gordov nhập ngũ Quân đội Đế quốc Nga năm 1915 và được thăng cấp trung sĩ. Ông tham gia Cận vệ Đỏ năm 1917, gia nhập Hồng quân năm 1918. Gordov kết thúc Nội chiến Nga với tư cách chỉ huy Trung đoàn súng trường số 53, chiến đấu trong chiến dịch chống lại Nestor Makhno, nhờ đó ông được trao tặng Huân chương Cờ đỏ.[1][3] Từ năm 1925 đến năm 1926, Gordov từng là cố vấn trong Quân đội Nhân dân Mông Cổ. Năm 1932, ông tốt nghiệp Học viện Quân sự Frunze và sau đó trở thành tham mưu trưởng Trường Bộ binh Cờ đỏ Moskva vào năm 1933. Ông là Tham mưu trưởng Sư đoàn Súng trường 18 từ tháng 5 năm 1935 đến năm 1937. Tháng 7 năm 1937, Gordov trở thành chỉ huy của Sư đoàn 67 súng trường. Tháng 7 năm 1939, ông trở thành Tham mưu trưởng Quân khu Kalinin.